Search Results

Documents authored by Teng, Shang-Hua

Document
DOI: 10.4230/LIPIcs.FUN.2022.10
Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
The concept of nimbers - a.k.a. Grundy-values or nim-values - is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, ℐ^P, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in ℐ^P is Sprague-Grundy-complete for ℐ^P. By viewing every impartial game as an encoding of its nimber - a succinct game secret richer than its winnability alone - our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for ℐ^P, there exists a polynomial-time algorithm to construct, for any pair of games G₁, G₂ in ℐ^P, a Generalized Geography game G satisfying: nimber(G) = nimber(G₁) ⊕ nimber(G₂).
Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.10,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10},
  URN =		{urn:nbn:de:0030-drops-159808},
  doi =		{10.4230/LIPIcs.FUN.2022.10},
  annote =	{Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.11
Quantum-Inspired Combinatorial Games: Algorithms and Complexity

Authors: Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Recently, quantum concepts inspired a new framework in combinatorial game theory. This transformation uses discrete superpositions to yield beautiful new rulesets with succinct representations that require sophisticated strategies. In this paper, we address the following fundamental questions: - Complexity Leap: Can this framework transform polynomial-time solvable games into intractable games? - Complexity Collapse: Can this framework transform PSPACE-complete games into ones with complexity in the lower levels of the polynomial-time hierarchy? We focus our study on how it affects two extensively studied polynomial-time-solvable games: Nim and Undirected Geography. We prove that both Nim and Undirected Geography make a complexity leap over NP, when starting with superpositions: The former becomes Σ₂^p-hard and the latter becomes PSPACE-complete. We further give an algorithm to prove that from any classical starting position, quantumized Undirected Geography remains polynomial-time solvable. Together they provide a nearly-complete characterization for Undirected Geography. Both our algorithm and its correctness proof require strategic moves and graph contraction to extend the matching-based theory for classical Undirected Geography. Our constructive proofs for both games highlight the intricacy of this framework. The polynomial time robustness of Undirected Geography in this quantum-inspired setting provides a striking contrast to the recent result that the disjunctive sum of two Undirected Geography games is PSPACE-complete. We give a Σ₂^p-hardness analysis of quantumized Nim, even if there are no pile sizes of more than 1.
Cite as

Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.FUN.2022.11,
  author =	{Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
  title =	{{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11},
  URN =		{urn:nbn:de:0030-drops-159812},
  doi =		{10.4230/LIPIcs.FUN.2022.11},
  annote =	{Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.24
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity

Authors: Wei Chen, Shang-Hua Teng, and Hanrui Zhang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We introduce two new "degree of complementarity" measures: supermodular width and superadditive width. Both are formulated based on natural witnesses of complementarity. We show that both measures are robust by proving that they, respectively, characterize the gap of monotone set functions from being submodular and subadditive. Thus, they define two new hierarchies over monotone set functions, which we will refer to as Supermodular Width (SMW) hierarchy and Superadditive Width (SAW) hierarchy, with foundations - i.e. level 0 of the hierarchies - resting exactly on submodular and subadditive functions, respectively. We present a comprehensive comparative analysis of the SMW hierarchy and the Supermodular Degree (SD) hierarchy, defined by Feige and Izsak. We prove that the SMW hierarchy is strictly more expressive than the SD hierarchy: Every monotone set function of supermodular degree d has supermodular width at most d, and there exists a supermodular-width-1 function over a ground set of m elements whose supermodular degree is m-1. We show that previous results regarding approximation guarantees for welfare and constrained maximization as well as regarding the Price of Anarchy (PoA) of simple auctions can be extended without any loss from the supermodular degree to the supermodular width. We also establish almost matching information-theoretical lower bounds for these two well-studied fundamental maximization problems over set functions. The combination of these approximation and hardness results illustrate that the SMW hierarchy provides not only a natural notion of complementarity, but also an accurate characterization of "near submodularity" needed for maximization approximation. While SD and SMW hierarchies support nontrivial bounds on the PoA of simple auctions, we show that our SAW hierarchy seems to capture more intrinsic properties needed to realize the efficiency of simple auctions. So far, the SAW hierarchy provides the best dependency for the PoA of Single-bid Auction, and is nearly as competitive as the Maximum over Positive Hypergraphs (MPH) hierarchy for Simultaneous Item First Price Auction (SIA). We also provide almost tight lower bounds for the PoA of both auctions with respect to the SAW hierarchy.
Cite as

Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2019.24,
  author =	{Chen, Wei and Teng, Shang-Hua and Zhang, Hanrui},
  title =	{{Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.24},
  URN =		{urn:nbn:de:0030-drops-101174},
  doi =		{10.4230/LIPIcs.ITCS.2019.24},
  annote =	{Keywords: set functions, measure of complementarity, submodularity, subadditivity, cardinality constrained maximization, welfare maximization, simple auctions, price of anarchy}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2018.1
Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk)

Authors: Shang-Hua Teng

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
What are efficient algorithms? What are network models? Big Data and Network Sciences have fundamentally challenged the traditional polynomial-time characterization of efficiency and the conventional graph-theoretical characterization of networks. More than ever before, it is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation. For a long time, graphs have been widely used for defining the structure of social and information networks. However, real-world network data and phenomena are much richer and more complex than what can be captured by nodes and edges. Network data are multifaceted, and thus network science requires a new theory, going beyond traditional graph theory, to capture the multifaceted data. In this talk, I discuss some aspects of these challenges. Using basic tasks in network analysis, social influence modeling, and machine learning as examples, I highlight the role of scalable algorithms and axiomatization in shaping our understanding of "effective solution concepts" in data and network sciences, which need to be both mathematically meaningful and algorithmically efficient.
Cite as

Shang-Hua Teng. Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{teng:LIPIcs.ISAAC.2018.1,
  author =	{Teng, Shang-Hua},
  title =	{{Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.1},
  URN =		{urn:nbn:de:0030-drops-99495},
  doi =		{10.4230/LIPIcs.ISAAC.2018.1},
  annote =	{Keywords: scalable algorithms, axiomatization, graph sparsification, local algorithms, advanced sampling, big data, network sciences, machine learning, social influence, beyond graph theory}
}
Document
DOI: 10.4230/DagSemProc.07391.1
07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms

Authors: Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking

Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)

Abstract
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. The seminar brought together leading researchers in probabilistic methods to strengthen and foster collaborations among various areas of Theoretical Computer Science. The interaction between researchers using randomization in algorithm design and researchers studying known algorithms and heuristics in probabilistic models enhanced the research of both groups in developing new complexity frameworks and in obtaining new algorithmic results. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking. 07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:DagSemProc.07391.1,
  author =	{Dietzfelbinger, Martin and Teng, Shang-Hua and Upfal, Eli and V\"{o}cking, Berthold},
  title =	{{07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms}},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7391},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.1},
  URN =		{urn:nbn:de:0030-drops-12915},
  doi =		{10.4230/DagSemProc.07391.1},
  annote =	{Keywords: Algorithms, Randomization, Probabilistic analysis, Complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact